package com.example.algorithm.service.impl;

import com.example.algorithm.service.HeapService;
import org.springframework.stereotype.Service;

import java.util.*;

/**
 * 堆
 * @auth Administrator
 * @create @2024/8/6@22:07
 * @decription
 **/
@Service
public class HeapServiceImpl implements HeapService {
    /**
     * NO.72 数组中的第k个最大元素
     * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
     *
     * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
     *
     * 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
     * @param nums
     * @param k
     * @return
     * 解法一：快排
     * 解法二：堆
     * 解法三：分治
     * 解法四：优先队列
     * 解法五：哈希表
     *
     */
    @Override
    public int findKthLargest(int[] nums, int k) {

        int heapSize =nums.length;
        // 构建最大堆
        for (int i = nums.length / 2 ; i >= 0; i--) {
            heapify(nums, nums.length, i);
        }
        for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
            swap(nums, 0, i);
            --heapSize;
            heapify(nums, 0, heapSize);
        }
        return nums[0];
    }

    /**NO.73 前k个高频元素
     * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
     * @param nums
     * @param k
     * @return
     * 解法一：堆
     * 解法二：快速排序
     * 解法三：桶排序
     *
     *
     */
    @Override
    public int[] topKFrequent(int[] nums, int k) {
        // 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值
        HashMap<Integer,Integer> map = new HashMap();
        for(int num : nums){
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        // 遍历map，用最小堆保存频率最大的k个元素
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                return map.get(a) - map.get(b);
            }
        });
        for (Integer key : map.keySet()) {
            if (pq.size() < k) {
                pq.add(key);
            } else if (map.get(key) > map.get(pq.peek())) {
                pq.remove();
                pq.add(key);
            }
        }
        return pq.stream().mapToInt(Integer::intValue).toArray();
    }

    /**
     * 堆排序
     * @param arr
     * @param heapSize
     * @param index
     */
    private void heapify(int[] arr, int heapSize, int index) {
        int left = index * 2 + 1;
        int right = index * 2 + 2;
        int largest = index;

        if (left < heapSize && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < heapSize && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != index) {
            swap(arr, index, largest);
            heapify(arr, heapSize, largest);
        }
    }

    /**
     * 交换
     * @param arr
     * @param i
     * @param j
     */
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
